"""
869. 重新排序得到 2 的幂
中等
相关标签
premium lock icon
相关企业
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。



示例 1：

输入：n = 1
输出：true
示例 2：

输入：n = 10
输出：false


提示：

1 <= n <= 109
"""


pow_two_sorted_str_set = {''.join(sorted(str(1 << i))) for i in range(30)}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        """
        根据题意，和十进制数字出现的次数有关，和顺序无关，直接遍历所有2的次幂的十进制，然后排序，之后对n进行同样操作寻找是否存在hashset中
        :param n:
        :return:
        """
        s = ''.join(sorted(str(n)))
        return s in pow_two_sorted_str_set

if __name__ == '__main__':
    print(Solution().reorderedPowerOf2(1))
    # print(bin(46))
    pow_two_sorted_str_set = {''.join(sorted(str(1 << i))) for i in range(30)}
